package primary.code02_Sort;

import java.util.Arrays;

/**
 * 归并排序 (稳定)
 * （递归方式实现，复杂度：N*logN）
 * 左右两侧有序后合并
 * 时间复杂度 O(N*logN)  空间复杂度 O(N)  稳定
 */
public class Code01_MergeSort {

    private static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) return;
//        mergeSort(arr, 0, arr.length - 1);
        mergeSortTest(arr, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int l, int r) {
        if (l == r) return;
        int m = (l + r) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
//        mergeTest(arr, l, m, r);
    }

    private static void mergeSortTest(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int m = (l + r) / 2;
        mergeSortTest(arr, l, m);
        mergeSortTest(arr, m + 1, r);
        mergeTest(arr, l, m, r);
    }

    /*归并过程*/
    private static void merge(int[] arr, int l, int m, int r) {
        int[] helper = new int[r - l + 1];
        int p1 = l;
        int p2 = m + 1;
        for (int i = 0; i < helper.length; i++) {
            if (p1 > m) helper[i] = arr[p2++];
            else if (p2 > r) helper[i] = arr[p1++];
            else helper[i] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];//<=的情况下，选择左边数组的元素，可以保持稳定性
        }
        for (int i = 0; i < helper.length; i++) {
            arr[l + i] = helper[i];
        }
    }

    private static void mergeTest(int[] arr, int l, int m, int r) {
        int[] helper = new int[r - l + 1];
        int p1 = l;
        int p2 = m + 1;
        int i = 0;
        while (p1 <= m && p2 <= r) {
            helper[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        for (int j = p1; j <= m; j++) {
            helper[i++] = arr[j];
        }
        for (int j = p2; j <= r; j++) {
            helper[i++] = arr[j];
        }
        for (int j = 0; j < helper.length; j++) {
            arr[l + j] = helper[j];
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 57, 87, 23, 57, 8, 1, 23, 587, 89};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
